The invention relates to programmable state machines and more particularly to programmable packet classification state machines for use in high-speed communication.
A current area of research in high-speed state machine design is the area of digital communications. Commonly, in digital communication networks, data is grouped into packets, cells, frames, buffers, and so forth. The packets, cells or so forth contain data and classification information. It is important to classify packets, cells, etc. for routing and correctly responding to data communications. An approach to classifying data of this type uses a state machine.
For Gigabit Ethernet, it is essential that a state machine operate at very high speeds to process data in order to determine addressing and routing information as well as protocol-related information. Unfortunately, at those speeds, memory access is a significant bottleneck in implementing a state machine or any other type of real time data processor. This is driving researchers to search for innovative solutions to increase classification performance. An obvious solution is to implement a classification state machine completely in hardware. Non-programmable hardware state machines are known to have unsurpassed performance and are therefore well suited to these high data rates; however, the implementation of communication protocols is inherently flexible in nature. A common protocol today may be all but obsolete in a few months. Therefore, it is preferable that a state machine for use with Gigabit Ethernet is programmable. In the past, solutions for 10 Mbit and 100 Mbit Ethernet data networks required many memory access instructions per state in order to accommodate programmability. This effectively limits operating speeds of the prior art state machines.
A programmable state machine for classification of data can be implemented entirely in software. Of course, software state machines are often much slower than their hardware equivalents. In a software state machine, each operation is performed by a software instruction and state changes result in branch operations. As is evident to those of skill in the art, to implement a high-speed state machine in software for packet classification, requires many instructions per secondxe2x80x94many more than a billionxe2x80x94requiring expensive parallel processors or technologies unknown at present. In fact, a severe limitation to performance is the speed of memory devices. For example, should a 7 ns memory device be used, less than one memory access per memory device is possible for each bit of a Gigabit Ethernet stream. Thus, if each bytexe2x80x948 bitsxe2x80x94of data is processed in a single state, only one memory access operations is possible for each state. To implement such a system as a purely software solution is unlikely.
Current state of the art integrated memory devices achieve performance in the area of 5 ns per memory access when timing and other factors are taken into account. Therefore, pure hardware implementations of state machines fast enough to implement a Gigabit Ethernet packet classifier are possible so long as only one memory access is required for every 8 bits within the Ethernet data stream. Prior art implementations of such a state machine use a branching algorithm to allow state transitions within the time frame of a predetermined number of bits. The address data for the branching algorithm is stored in program memory. When the predetermined number of bits is 8, each state transition occurs within 8 ns. One method of achieving this performance is to store a table of data having 256 entries for each possible state. The table address is then concatenated with 8 bits from the data stream to determine a next state address. This continues until a value indicative of a classification or a failure to classify is encountered.
Unfortunately, the amount of memory required to implement a system, such as that described above, is prohibitive. For example, using 8 bits at a time requires 256 entries per table, 16 bits at a time requires 65,536 entries. The exact number of tables also depends on a number of terminal states. Since integrated memory having a high storage capacity is not available, implementation of a prior art programmable packet classification state machines having large numbers of edges in integrated memory is currently not feasible.
It would be advantageous to provide a state-machine for classification of bits in a data stream requiring only one memory access to program memory per state transition.
It has been found that a programmable state machine for use in packet classification of high-speed data communications wherein program memory requirements are reduced over program memory requirements of prior art implementations would be highly advantageous.
In order to overcome these and other limitations of the prior art, it is an object of the invention to provide a state machine architecture for supporting implementation of high speed packet classification and providing for reduced memory requirements over those necessary in the prior art.
It is another object of the present invention to provide state machine architecture for supporting implementation of high-speed packet classification and requiring only one memory access to program memory for each state transition.
It is another object of the present invention to provide state machine architecture for supporting programmable high-speed packet classification.
Accordingly, the invention provides a packet classification state machine for classifying data from a data stream. The state machine comprises:
a) a programmable memory for storing information relating to states within the state machine, the states including a first group of states and a second group of states, the first group of states each represented by a table of data at a table address and including a first plurality of table elements addressable at an offset from the table address, each of the table elements indicative of a next state within the state machine, and the second group of states each represented by a table of data including a table element and occupying less memory than a table of data representing a state of the first group of states; and,
b) a processor for determining a next state based on contents of a table element of a present state at an offset from the table address, the offset determined during a table address load portion of an instruction cycle in dependence upon the bits in the data stream, the processor also for switching the state machine into the next state so determined.
According to another embodiment, the invention provides a packet classification state machine for classifying data from a data stream. The state machine comprises:
a) a programmable memory for storing information relating to states within the state machine, the states including three groups of states;
the first group of states each represented by a table of data including 2n table elements addressable at an offset from the table address, the table elements indicative of a next state within the state machine, n bits in the data stream for determining the offset,
the second group of states each represented by a table of data including 2n table elements having a size smaller than that of table elements of the first group of states, the table elements addressable at an offset from the table address, the table elements indicative of a next state within the state machine, n bits in the data stream for determining the offset; and
the third group of states each represented by data indicative of a single possible next state; and,
c) a processor for storing for a table address of the first group a current state address and a plurality of bits from the data stream together to form an address, for a table address of the second group a current state address and a plurality of bits from the data stream together to form an address, and for a table address of the third group a current state address; for retrieving from that address in the programmable memory an operation, the operations comprising a jump operation including data relating to a next state address; for determining the next state based on one of information within the operation; and for switching the state machine into the next state,
wherein one and only one operation retrieving information from the programmable memory is performed between successive state transitions.
According to another aspect of the invention, there is provided a method of packet classification for classifying data from a data stream. The method comprises the following steps:
a) providing classification data comprising information relating to states within a state machine, the states including a first group of states and a second group of states,
the first group of states each represented by a table of data at a table address including a first plurality of table elements addressable at an offset from the table address, each of the table elements indicative of a next state within the state machine, and
the second group of states each represented by a table of data including a table element and occupying less memory than a table of data representing a state of the first group of states;
b) providing a table address of a current state;
c) selecting a table element, the table element selected in dependence upon the table address, the table contents, and an offset based on a plurality of bits in the data stream;
d) determining a next state of the state machine based on the content of the selected element of a present state; and,
e) switching the state machine into the next state so determined.